#include <stdio.h>

void PrintArray(int *a,int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//冒泡排序
void BubbleSort(int *a, int size)
{
    for(int i = 0; i < size - 1; i++)   //将n个数归位置
    {
        int flag = 0;
        for(int j = 0; j < size - i - 1; j++)   //两两比较
        {
            if(a[j] > a[j+1])
            //if(a[j] < a[j+1])
            {
                flag = 1;
                Swap(&a[j], &a[j+1]);
            }
        }
        if(flag == 0)  //数列已经有序
        {
            break;  //跳出循环
        }
    }
}

//插入排序
void InsertSort(int *a, int size)
{
    for(int i = 1; i < size; i++)
    {
        int j = i;  //这个位置使即将要插入的数的值
        int temp  = a[j];
        for(; j > 0; j--)
        {
            //if(a[j-1] > temp) //前面的数比我大
            if(a[j-1] < temp)
            {
                a[j] = a[j-1];
            }
            else    //前面的数不比我大，跳出循环
            {
                break;
            }
        }
        a[j] = temp;
    }
}

//选择排序
void ChooseSort(int *a,int size)
{
    for(int i = 0; i < size - 1; i++)
    {
        int min = i;
        for(int j = i+1; j < size; j++)
        {
            if(a[min] > a[j])
            //if(a[min] < a[j])
            {
                min = j;
            }
        }
        Swap(&a[min],&a[i]);
    }
}

//双指针算法
void ChooseSort2(int *a,int size)
{
    int left = 0;
    int right = size - 1;
    while( left < right)
    {
        int min = left;
        int max = right;
        // for(int i = left; i <= right; i++)
        // {
        //     if(a[i] < a[min])
        //         min = i;
        //     if(a[i] > a[max])
        //         max = i;
        // }
        for(int i = left; i <= right; i++)
        {
            if(a[i] > a[min])
                min = i;
            if(a[i] < a[max])
                max = i;
        }
        Swap(&a[left],&a[min]);
        if(max == left)   //极值在两端
        {
            max = min;
        }
        Swap(&a[right],&a[max]);  //极值在两端会有问题
        left++;
        right--;
    }
}

//快速排序  双指针  递归  分治
void FastSort(int *a, int start, int end)
{
    //终止条件
    if(start >= end)
        return;
    int left = start;
    int right = end;
    int temp = a[start];
    while(left < right)
    {
        //从右往左找比基准值小的值
        while(a[right] > temp && left < right)
        //while(a[right] < temp && left < right)
            right--;
        if(left < right)
            a[left++] = a[right];  //把比基准值小的数放到左边


        //从左往右找比基准值大的值
        while(a[left] < temp && left < right)
        //while(a[left] > temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];  //把比基准值大的数放到右边

    }
    a[left] = temp;

    FastSort(a, start, left - 1);
    FastSort(a, right + 1, end);
}

//返回找到的数组元素的下标
int BinarySearch(int *a,int size, int element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        int mid  = left + (right - left) / 2;
                //(left & right) + ((left ^ right)>>1);
        if(a[mid] == element)
        {
            return mid;
        }
        else if(a[mid] > element)
        {
            right = mid - 1;
        }
        else if(a[mid] < element)
        {
            left = mid + 1;
        }
    }
    return -1;
}

int main()
{
    int a[] = {40,3,65,1,46,24,100,45,2};
    PrintArray(a,sizeof(a)/sizeof(a[0])); //sizeof(a)/sizeof(a[0])

    //BubbleSort(a,sizeof(a)/sizeof(a[0]));
    //InsertSort(a,sizeof(a)/sizeof(a[0]));
    //ChooseSort(a,sizeof(a)/sizeof(a[0]));
    //ChooseSort2(a,sizeof(a)/sizeof(a[0]));
    FastSort(a,0,sizeof(a)/sizeof(a[0])-1);
    PrintArray(a,sizeof(a)/sizeof(a[0]));

    // int index = BinarySearch(a,sizeof(a)/sizeof(a[0]),100);
    // if(index == -1)
    // {
    //     printf("没找到!\n");
    // }
    // else
    // {
    //     printf("找到了，在%d位置\n", index);
    // }
    return 0;
}